package sample.xiaosong.basicsort;

import java.util.Arrays;

/**
 * @author xiaosong
 */
public class BasicSort {
    public static void main(String[] args) {
        int maxSize = 100;
        int maxValue = 150;
        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        mergeSort(arr);
        printArray(arr);

        int[] arr1 = generateRandomArray(maxSize, maxValue);
        printArray(arr1);
        bubbleSort(arr1);
        printArray(arr1);

        int[] arr2 = generateRandomArray(maxSize, maxValue);
        printArray(arr2);
        selectionSort(arr2);
        printArray(arr2);

        int[] arr3 = generateRandomArray(maxSize, maxValue);
        printArray(arr3);
        insertionSort(arr3);
        printArray(arr3);

        int[] arr4 = generateRandomArray(maxSize, maxValue);
        printArray(arr4);
        quickSort(arr4);
        printArray(arr4);

        int[] arr5 = generateRandomArray(maxSize, maxValue);
        printArray(arr5);
        heapSort(arr5);
        printArray(arr5);

        int[] arr6 = generateRandomArray(maxSize, maxValue);
        printArray(arr6);
        countSort(arr6);
        printArray(arr6);

    }

    public static void mergeSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        process(array, 0, array.length - 1);
    }

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j +1);
                }
            }
        }
    }

    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                minIndex = array[j] < array[minIndex] ? j : minIndex;
            }
            swap(array, i, minIndex);
        }
    }

    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i -1 ; j >= 0 && array[j] > array[j + 1]; j--) {
                swap(array, j, j + 1);
            }
        }
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] array, int l, int r) {
        if (l < r) {
            swap(array, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(array, l, r);
            quickSort(array, l, p[0] - 1);
            quickSort(array, p[1] + 1, r);
        }
    }

    public static void heapSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        // 将数组元素转化为大顶堆
        for (int i = 0; i < array.length; i++) {
            heapInsert(array, i);
        }
        int size = array.length;
        // 将最后一个元素放到堆顶，同时缩短长度，约等于将堆顶最大的节点删除(放到了最后)
        swap(array, 0, --size);
        while (size > 0) {
            // 堆删除节点之后重新变成大顶数的过程
            heapify(array, 0, size);
            // 删除头节点
            swap(array, 0, --size);
        }
    }

    public static void countSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            maxValue = Math.max(maxValue, array[i]);
        }
        int[] bucket = new int[maxValue + 1];
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                array[i++] = j;
            }
        }
    }

    /**
     * 当前节点与父节点比较，如果比父节点大，交换当前节点与父节点，当前节点变成父节点继续向上对比
     */
    public static void heapInsert(int[] array, int index) {
        while (array[index] > array[(index - 1) / 2]) {
            swap(array, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] array, int index, int size) {
        // 预定左节点为较大的节点
        int left = index * 2 + 1;
        while (left < size) {
            // 比较左右两个子节点，取大的节点往下比较
            int largest = left + 1 < size && array[left + 1] > array[left] ? left + 1 : left;
            // 比较当前节点与子节点中最大的那个节点，记录最大节点
            largest = array[largest] > array[index] ? largest : index;
            //如果当前节点比子节点都大，直接退出
            if (largest == index) {
                break;
            }
            // 交换当前节点与子节点的位置
            swap(array, index, largest);
            // 更新当前节点
            index = largest;
            // 更新左子节点
            left = index * 2 + 1;
        }
    }

    /**
     * array[r] 为被选定的num值
     */
    public static int[] partition(int[] array, int l, int r) {
        int less = l - 1; // 小于区域的右边界
        int more = r; //大于区域的左边界
        while (l < more) {
            if (array[l] < array[r]) {
                swap(array, ++less, l++);//放到小于区域右边界前面,并扩大小于区域
            } else if (array[l] > array[r]) {
                swap(array, --more, l);//放到大于区域左边界前面,并扩大大于区域
            } else {
                l++;//等于区域直接右移
            }
        }
        swap(array, more, r);// 将大于的数放到最右边
        return new int[] {less + 1, more};
    }

    public static void process(int[] array, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        process(array, l, mid);
        process(array, mid + 1, r);
        merge(array, l, mid, r);
    }

    public static void merge(int[] array, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            help[i++] = array[p1] <= array[p2] ? array[p1++] : array[p2++];
        }
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= r) {
            help[i++] = array[p2++];
        }
        for (i = 0; i < help.length; i ++) {
            array[l + i] = help[i];
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}
